/*
 * 循环队列 - 只能存储n-1个元素
 */
#include <stdio.h>
#include <string.h>


#define QUEUE_SIZE	5

/* type */
struct Student {
    int id;
    char name[100];
    int age;
    char sex;
};
typedef struct Student ElemType;
//typedef int ElemType;


/*
 *
 */
struct queue {
	ElemType data[QUEUE_SIZE];
	int front; /* 头指针 */
	int rear;  /* 尾指针，若队列不为空，指向队列尾元素的下一个位置 */
};

typedef struct queue queue_t;



/*
 *
 */
void
init_queue(queue_t *queue)
{
	memset(queue, 0, sizeof(queue_t));
	queue->front = 0;
	queue->rear = 0;
}


int
queue_length(queue_t *q)
{
	return (q->rear - q->front + QUEUE_SIZE) % QUEUE_SIZE;
}


/*
 *
 */
int
enqueue(queue_t *q, ElemType *item)
{
	/* if full */
	if ((q->rear + 1) % QUEUE_SIZE == q->front)
		return -1;

	q->data[q->rear] = *item;
	q->rear = (q->rear + 1) % QUEUE_SIZE; /* 尾指针向后移一位，若到最后则转到数组头部 */

	return 0;
}

/*
 *
 */
int
dequeue(queue_t *q, ElemType *item)
{
	/* if empty */ 
	if (q->front == q->rear)
		return -1;

	*item = q->data[q->front];
	q->front = (q->front + 1) % QUEUE_SIZE; /* 头指针向后移一位，若到最后则转到数组头部 */

	return 0;
}

/*
 * 清空队列
 */
int
clear_queue(queue_t *q)
{
    init_queue(q);
    return 0;
}

/*
 * 获取队列头元素
 */
int
get_queue_head(queue_t *q, ElemType *item)
{
	/* if empty */ 
	if (q->front == q->rear)
		return -1;
    
    *item = q->data[q->front];
    
    return 0;
}


/******************************************************************************/


int
main(void)
{
    queue_t queue;
    int i, ret;
    ElemType item;

    init_queue(&queue);



    printf("After init, length = %d\n", queue_length(&queue));


    /* 插入10个节点 */
    for (i = 0; i < 10; ++i) {
        memset(&item, 0, sizeof(item));
        item.id = i+1;
        snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
        printf("enqueue() item[%d] ret[%d]\n", i, enqueue(&queue, &item));
    }
    printf("\n");
    printf("After enqueue, length = %d\n", queue_length(&queue));



    memset(&item, 0, sizeof(item));
    get_queue_head(&queue, &item);
    printf("After enqueue, top item: Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);


    printf("\n");
    /* 删除10个节点 */
    for (i = 0; i < 10; ++i) {
        memset(&item, 0, sizeof(item));
        ret = dequeue(&queue, &item);
        printf("dequeue() item[%d] ret[%d]\n", i, ret);
        if (ret == 0)
            printf("-- Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);
    }
    printf("After dequeue, length = %d\n", queue_length(&queue));


    clear_queue(&queue);
    clear_queue(&queue);

    printf("\n");
    printf("After clear, length = %d\n", queue_length(&queue));


    /* 插入6个节点 */
    for (i = 0; i < 6; ++i) {
        memset(&item, 0, sizeof(item));
        item.id = i+1;
        snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
        printf("enqueue() item[%d] ret[%d]\n", i, enqueue(&queue, &item));
    }
    printf("\n");
    printf("After enqueue, length = %d\n", queue_length(&queue));


    memset(&item, 0, sizeof(item));
    get_queue_head(&queue, &item);
    printf("After enqueue, top item: Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);


    /* 删除2个节点 */
    for (i = 0; i < 2; ++i) {
        memset(&item, 0, sizeof(item));
        ret = dequeue(&queue, &item);
        printf("dequeue() item[%d] ret[%d]\n", i, ret);
        if (ret == 0)
            printf("-- Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);
    }
    printf("After dequeue, length = %d\n", queue_length(&queue));
    
    clear_queue(&queue);

    printf("\n");
    printf("After clear, length = %d\n", queue_length(&queue));


    return 0;
}


/******************************************************************************/

struct node {
	int capacity;
	int front;
	int rear;
	int size;
	int *array;
};

typedef struct node queue_t;

queue_t *
create_queue(int size)
{
	queue_t *q;

	q = malloc(sizeof(queue_t));
	q->capacity = size;
	q->array = malloc(sizeof(int) * size);
	make_empty(q);
}

int
isempty(queue_t *q)
{
	return (q->size == 0);
}

voif
make_empty(queue_t *q)
{
	q->size = 0;
	q->front = 1;
	q->rear = 0;
}

int
isfull(queue_t *q)
{
	return (q->size == q->capacity);
}

int
succ(queue_t *q, int value)
{
	if (++value == q->capacity)
		return 0;
	return value;
}

void
enqueue(queue_t *q, int item)
{
	if (isfull(q))
		error;
	else {
		q->size++;
		q->rear = succ(q, q->rear);
		q->array[q->rear] = item;
	}
}

int
dequeue(queue_t *q)
{
	int tmp;
	if (isempty(q))
		error;
	else {
		q->size--;
		tmp = q->array[q->front];
		q->front = succ(q, q->front);
	}
	return tmp;
}




